package subject_set.weekly_competition.day10_9;

/**
 * @author haomin
 * @date 2022/10/09 12:01
 **/
public class Num4 {
    class Solution {
        int ans = 0;
        public int numberOfPaths(int[][] grid, int k) {
            dfs(grid, 0, 0, grid.length-1, grid[0].length-1, 0, k);
            return ans;
        }
        private void dfs(int[][] grid, int i, int j, int m, int n, int sum, int k){
            if(i > m || j > n) return;
            sum += grid[i][j];
            if(i == m && j == n){
                if(sum % k == 0) ans ++;
            }
            dfs(grid, i, j+1, m, n, sum, k);
            dfs(grid, i+1, j, m, n, sum, k);
        }
    }
    class Solution2 {
        public int numberOfPaths(int[][] grid, int k) {
            ////给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

            //请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果。


            int m = grid.length;
            int n = grid[0].length;
            int mod = 1000000007;

            int[][][] dp = new int[m][n][k + 1]; //dp[i][j][l]表示从(0,0)到(i,j)的路径和为l的路径数目
            dp[0][0][grid[0][0] % k] = 1; //初始化

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    for (int l = 0; l <= k; l++) {
                        if (i > 0) {
                            dp[i][j][l] = (dp[i][j][l] + dp[i - 1][j][(l - grid[i][j] % k + k) % k]) % mod;
                        }
                        if (j > 0) {
                            dp[i][j][l] = (dp[i][j][l] + dp[i][j - 1][(l - grid[i][j] % k + k) % k]) % mod;
                        }
                    }
                }
            }

            return dp[m - 1][n - 1][0];
        }
    }
}